package graph;

import java.util.Arrays;

/**
 * 给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，每个节点 至多 有一条出边。
 * 有向图用大小为 n 下标从 0 开始的数组 edges 表示，表示节点 i 有一条有向边指向 edges[i] 。如果节点 i 没有出边，那么 edges[i] == -1 。
 * 同时给你两个节点 node1 和 node2 。
 * 请你返回一个从 node1 和 node2 都能到达节点的编号，使节点 node1 和节点 node2 到这个节点的距离 较大值最小化。如果有多个答案，请返回
 * 最小 的节点编号。如果答案不存在，返回 -1 。
 * 注意 edges 可能包含环。
 * <p>
 * 示例 1：
 * 输入：edges = [2,2,3,-1], node1 = 0, node2 = 1
 * 输出：2
 * 解释：从节点 0 到节点 2 的距离为 1 ，从节点 1 到节点 2 的距离为 1 。
 * 两个距离的较大值为 1 。我们无法得到一个比 1 更小的较大值，所以我们返回节点 2 。
 * <p>
 * 示例 2：
 * 输入：edges = [1,2,-1], node1 = 0, node2 = 2
 * 输出：2
 * 解释：节点 0 到节点 2 的距离为 2 ，节点 2 到它自己的距离为 0 。
 * 两个距离的较大值为 2 。我们无法得到一个比 2 更小的较大值，所以我们返回节点 2 。
 *
 * @author Jisheng Huang
 * @version 20250530
 */
public class ClosestMeetingNode_2359 {
    /**
     * 题目给定一个 n 个节点的有向图，每个节点至多有一个出边。因此，我们从某个点（设为 x）出发不断地沿着出边（最多一条）遍历，得到 x 可以
     * 到达的所有点，以及距离。这一过程可以用循环来实现，直到某个点无出边或者这个点已被遍历过时停止。
     * <p>
     * 分别对 node1 和 node2按照上述步骤计算后，遍历所有点，筛选出 node1 和 node2 都可以到达的点，
     * 并从中选出离 node1 和 node2 最远距离最小的点即可。
     *
     * @param edges
     * @param node1
     * @param node2
     * @return
     */
    public static int closestMeetingNode(int[] edges, int node1, int node2) {
        int n = edges.length;
        int[] d1 = get(edges, node1);
        int[] d2 = get(edges, node2);

        int res = -1;

        for (int i = 0; i < n; ++i) {
            if (d1[i] != -1 && d2[i] != -1) {
                if (res == -1 || Math.max(d1[res], d2[res]) > Math.max(d1[i], d2[i])) {
                    res = i;
                }
            }
        }

        return res;
    }

    /**
     * helper method
     *
     * @param edges
     * @param node
     * @return
     */
    public static int[] get(int[] edges, int node) {
        int n = edges.length;
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        int distance = 0;

        while (node != -1 && dist[node] == -1) {
            dist[node] = distance++;
            node = edges[node];
        }

        return dist;
    }

    public static void main(String[] args) {
        int[] edges = {2, 2, 3, -1};
        int node1 = 0;
        int node2 = 1;

        System.out.println(closestMeetingNode(edges, node1, node2));
    }

}
